<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="English" xml:lang="English">
<head>
<!-- 2023-02-21 Di 18:07 -->
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>The Seasoned Schemer Notes</title>
<meta name="author" content="Zelphir Kaltstahl" />
<meta name="generator" content="Org Mode" />
<style>
  #content { max-width: 60em; margin: auto; }
  .title  { text-align: center;
             margin-bottom: .2em; }
  .subtitle { text-align: center;
              font-size: medium;
              font-weight: bold;
              margin-top:0; }
  .todo   { font-family: monospace; color: red; }
  .done   { font-family: monospace; color: green; }
  .priority { font-family: monospace; color: orange; }
  .tag    { background-color: #eee; font-family: monospace;
            padding: 2px; font-size: 80%; font-weight: normal; }
  .timestamp { color: #bebebe; }
  .timestamp-kwd { color: #5f9ea0; }
  .org-right  { margin-left: auto; margin-right: 0px;  text-align: right; }
  .org-left   { margin-left: 0px;  margin-right: auto; text-align: left; }
  .org-center { margin-left: auto; margin-right: auto; text-align: center; }
  .underline { text-decoration: underline; }
  #postamble p, #preamble p { font-size: 90%; margin: .2em; }
  p.verse { margin-left: 3%; }
  pre {
    border: 1px solid #e6e6e6;
    border-radius: 3px;
    background-color: #f2f2f2;
    padding: 8pt;
    font-family: monospace;
    overflow: auto;
    margin: 1.2em;
  }
  pre.src {
    position: relative;
    overflow: auto;
  }
  pre.src:before {
    display: none;
    position: absolute;
    top: -8px;
    right: 12px;
    padding: 3px;
    color: #555;
    background-color: #f2f2f299;
  }
  pre.src:hover:before { display: inline; margin-top: 14px;}
  /* Languages per Org manual */
  pre.src-asymptote:before { content: 'Asymptote'; }
  pre.src-awk:before { content: 'Awk'; }
  pre.src-authinfo::before { content: 'Authinfo'; }
  pre.src-C:before { content: 'C'; }
  /* pre.src-C++ doesn't work in CSS */
  pre.src-clojure:before { content: 'Clojure'; }
  pre.src-css:before { content: 'CSS'; }
  pre.src-D:before { content: 'D'; }
  pre.src-ditaa:before { content: 'ditaa'; }
  pre.src-dot:before { content: 'Graphviz'; }
  pre.src-calc:before { content: 'Emacs Calc'; }
  pre.src-emacs-lisp:before { content: 'Emacs Lisp'; }
  pre.src-fortran:before { content: 'Fortran'; }
  pre.src-gnuplot:before { content: 'gnuplot'; }
  pre.src-haskell:before { content: 'Haskell'; }
  pre.src-hledger:before { content: 'hledger'; }
  pre.src-java:before { content: 'Java'; }
  pre.src-js:before { content: 'Javascript'; }
  pre.src-latex:before { content: 'LaTeX'; }
  pre.src-ledger:before { content: 'Ledger'; }
  pre.src-lisp:before { content: 'Lisp'; }
  pre.src-lilypond:before { content: 'Lilypond'; }
  pre.src-lua:before { content: 'Lua'; }
  pre.src-matlab:before { content: 'MATLAB'; }
  pre.src-mscgen:before { content: 'Mscgen'; }
  pre.src-ocaml:before { content: 'Objective Caml'; }
  pre.src-octave:before { content: 'Octave'; }
  pre.src-org:before { content: 'Org mode'; }
  pre.src-oz:before { content: 'OZ'; }
  pre.src-plantuml:before { content: 'Plantuml'; }
  pre.src-processing:before { content: 'Processing.js'; }
  pre.src-python:before { content: 'Python'; }
  pre.src-R:before { content: 'R'; }
  pre.src-ruby:before { content: 'Ruby'; }
  pre.src-sass:before { content: 'Sass'; }
  pre.src-scheme:before { content: 'Scheme'; }
  pre.src-screen:before { content: 'Gnu Screen'; }
  pre.src-sed:before { content: 'Sed'; }
  pre.src-sh:before { content: 'shell'; }
  pre.src-sql:before { content: 'SQL'; }
  pre.src-sqlite:before { content: 'SQLite'; }
  /* additional languages in org.el's org-babel-load-languages alist */
  pre.src-forth:before { content: 'Forth'; }
  pre.src-io:before { content: 'IO'; }
  pre.src-J:before { content: 'J'; }
  pre.src-makefile:before { content: 'Makefile'; }
  pre.src-maxima:before { content: 'Maxima'; }
  pre.src-perl:before { content: 'Perl'; }
  pre.src-picolisp:before { content: 'Pico Lisp'; }
  pre.src-scala:before { content: 'Scala'; }
  pre.src-shell:before { content: 'Shell Script'; }
  pre.src-ebnf2ps:before { content: 'ebfn2ps'; }
  /* additional language identifiers per "defun org-babel-execute"
       in ob-*.el */
  pre.src-cpp:before  { content: 'C++'; }
  pre.src-abc:before  { content: 'ABC'; }
  pre.src-coq:before  { content: 'Coq'; }
  pre.src-groovy:before  { content: 'Groovy'; }
  /* additional language identifiers from org-babel-shell-names in
     ob-shell.el: ob-shell is the only babel language using a lambda to put
     the execution function name together. */
  pre.src-bash:before  { content: 'bash'; }
  pre.src-csh:before  { content: 'csh'; }
  pre.src-ash:before  { content: 'ash'; }
  pre.src-dash:before  { content: 'dash'; }
  pre.src-ksh:before  { content: 'ksh'; }
  pre.src-mksh:before  { content: 'mksh'; }
  pre.src-posh:before  { content: 'posh'; }
  /* Additional Emacs modes also supported by the LaTeX listings package */
  pre.src-ada:before { content: 'Ada'; }
  pre.src-asm:before { content: 'Assembler'; }
  pre.src-caml:before { content: 'Caml'; }
  pre.src-delphi:before { content: 'Delphi'; }
  pre.src-html:before { content: 'HTML'; }
  pre.src-idl:before { content: 'IDL'; }
  pre.src-mercury:before { content: 'Mercury'; }
  pre.src-metapost:before { content: 'MetaPost'; }
  pre.src-modula-2:before { content: 'Modula-2'; }
  pre.src-pascal:before { content: 'Pascal'; }
  pre.src-ps:before { content: 'PostScript'; }
  pre.src-prolog:before { content: 'Prolog'; }
  pre.src-simula:before { content: 'Simula'; }
  pre.src-tcl:before { content: 'tcl'; }
  pre.src-tex:before { content: 'TeX'; }
  pre.src-plain-tex:before { content: 'Plain TeX'; }
  pre.src-verilog:before { content: 'Verilog'; }
  pre.src-vhdl:before { content: 'VHDL'; }
  pre.src-xml:before { content: 'XML'; }
  pre.src-nxml:before { content: 'XML'; }
  /* add a generic configuration mode; LaTeX export needs an additional
     (add-to-list 'org-latex-listings-langs '(conf " ")) in .emacs */
  pre.src-conf:before { content: 'Configuration File'; }

  table { border-collapse:collapse; }
  caption.t-above { caption-side: top; }
  caption.t-bottom { caption-side: bottom; }
  td, th { vertical-align:top;  }
  th.org-right  { text-align: center;  }
  th.org-left   { text-align: center;   }
  th.org-center { text-align: center; }
  td.org-right  { text-align: right;  }
  td.org-left   { text-align: left;   }
  td.org-center { text-align: center; }
  dt { font-weight: bold; }
  .footpara { display: inline; }
  .footdef  { margin-bottom: 1em; }
  .figure { padding: 1em; }
  .figure p { text-align: center; }
  .equation-container {
    display: table;
    text-align: center;
    width: 100%;
  }
  .equation {
    vertical-align: middle;
  }
  .equation-label {
    display: table-cell;
    text-align: right;
    vertical-align: middle;
  }
  .inlinetask {
    padding: 10px;
    border: 2px solid gray;
    margin: 10px;
    background: #ffffcc;
  }
  #org-div-home-and-up
   { text-align: right; font-size: 70%; white-space: nowrap; }
  textarea { overflow-x: auto; }
  .linenr { font-size: smaller }
  .code-highlighted { background-color: #ffff00; }
  .org-info-js_info-navigation { border-style: none; }
  #org-info-js_console-label
    { font-size: 10px; font-weight: bold; white-space: nowrap; }
  .org-info-js_search-highlight
    { background-color: #ffff00; color: #000000; font-weight: bold; }
  .org-svg { }
</style>
</head>
<body>
<div id="content" class="content">
<h1 class="title">The Seasoned Schemer Notes
<br />
<span class="subtitle">Chapter 12</span>
</h1>
<div id="table-of-contents" role="doc-toc">
<h2>Table of Contents</h2>
<div id="text-table-of-contents" role="doc-toc">
<ul>
<li><a href="#org62281e9">1. Prerequisites</a>
<ul>
<li><a href="#org1002358">1.1. Y-combinator</a></li>
</ul>
</li>
<li><a href="#org3ba08b7">2. Chapter 12</a>
<ul>
<li><a href="#org7d9c57a">2.1. Recap of Y</a></li>
<li><a href="#org7bdbb9d">2.2. Introduction of <code>letrec</code></a></li>
<li><a href="#orgc07ab58">2.3. <code>multirember</code> with configurable <code>test?</code> predicate</a></li>
<li><a href="#org3d9907f">2.4. Set union implementation</a></li>
</ul>
</li>
</ul>
</div>
</div>

<div id="outline-container-org62281e9" class="outline-2">
<h2 id="org62281e9"><span class="section-number-2">1.</span> Prerequisites</h2>
<div class="outline-text-2" id="text-1">
<div class="org-src-container">
<pre class="src src-scheme" id="org73733f4">(define atom?
  (λ (x)
    (and (not (pair? x))
         (not (null? x)))))
</pre>
</div>

<p>
In theory we could define other things as numbers, for example church numerals.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgb701474">(define one?
  (λ (x)
    (= x 1)))
</pre>
</div>

<div class="org-src-container">
<pre class="src src-scheme" id="org266a651">(define pick
  (λ (n lat)
    (cond
     [(one? n) (car lat)]
     [else
      (pick (- n 1) (cdr lat))])))
</pre>
</div>
</div>

<div id="outline-container-org1002358" class="outline-3">
<h3 id="org1002358"><span class="section-number-3">1.1.</span> Y-combinator</h3>
<div class="outline-text-3" id="text-1-1">
<p>
In the first book the Y-combinator was derived. It is again:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org3ae2c04">(define Y
  (λ (proc)
    ((λ (f) (f f))
     (λ (f)
       (proc
        (λ (x) ((f f) x)))))))
</pre>
</div>
</div>
</div>
</div>

<div id="outline-container-org3ba08b7" class="outline-2">
<h2 id="org3ba08b7"><span class="section-number-2">2.</span> Chapter 12</h2>
<div class="outline-text-2" id="text-2">
</div>
<div id="outline-container-org7d9c57a" class="outline-3">
<h3 id="org7d9c57a"><span class="section-number-3">2.1.</span> Recap of Y</h3>
<div class="outline-text-3" id="text-2-1">
</div>
<div id="outline-container-org45f1193" class="outline-4">
<h4 id="org45f1193"><span class="section-number-4">2.1.1.</span> Recursive <code>length</code> function using <code>Y</code></h4>
<div class="outline-text-4" id="text-2-1-1">
<p>
The length function is injected as an argument. Thus the expression is not referring to itself, but only ever to its argument.
</p>

<p>
The inner part looks just like the usual recursive length function. It is using an argument (<code>length</code>) as the thing it calls in the recursive case though.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org5d558ae">(define Y
  (λ (proc)
    ((λ (f) (f f))
     (λ (f)
       (proc
        (λ (x) ((f f) x)))))))

(define length
  (Y (λ (length)
       (λ (lst)
         (cond
          [(null? lst) 0]
          [else
           (+ (length (cdr lst)) 1)])))))

(simple-format #t "(length '(a b c d)) = ~a\n" (length '(a b c d)))
</pre>
</div>

<pre class="example" id="orgf052f54">
(length '(a b c d)) = 4
</pre>
</div>
</div>

<div id="outline-container-org7bbcf85" class="outline-4">
<h4 id="org7bbcf85"><span class="section-number-4">2.1.2.</span> <code>multirember</code> (remove member multiple times) function using <code>Y</code></h4>
<div class="outline-text-4" id="text-2-1-2">
<p>
The argument of <code>Y</code> is always a lambda expression, which takes as argument the function to be called in the recursive case. That function itself returns a function, which takes the actual input. In this example that is a list of atoms.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orga94e6ec">(define Y
  (λ (proc)
    ((λ (f) (f f))
     (λ (f)
       (proc
        (λ (x) ((f f) x)))))))

(define multirember
  (λ (a lat)
    ((Y (λ (mr)
          (λ (lat)
            (cond
             [(null? lat) '()]
             [(eq? a (car lat))
              (mr (cdr lat))]
             [else
              (cons (car lat)
                    (mr (cdr lat)))]))))
     lat)))
</pre>
</div>
</div>

<div id="outline-container-orga7cdd06" class="outline-5">
<h5 id="orga7cdd06"><span class="section-number-5">2.1.2.1.</span> Usage</h5>
<div class="outline-text-5" id="text-2-1-2-1">
<div class="org-src-container">
<pre class="src src-scheme" id="orgefe9736">(multirember 'a '(a b c a d))
</pre>
</div>
</div>
</div>

<div id="outline-container-orgc6a6ae5" class="outline-5">
<h5 id="orgc6a6ae5"><span class="section-number-5">2.1.2.2.</span> Results</h5>
<div class="outline-text-5" id="text-2-1-2-2">
<pre class="example" id="orgbb0d937">
(b c d)
</pre>
</div>
</div>
</div>
</div>

<div id="outline-container-org7bdbb9d" class="outline-3">
<h3 id="org7bdbb9d"><span class="section-number-3">2.2.</span> Introduction of <code>letrec</code></h3>
<div class="outline-text-3" id="text-2-2">
<p>
<code>letrec</code> offers a way to avoid using <code>Y</code> and possibly get a more easily understandable definition of recursive functions.
</p>
</div>

<div id="outline-container-org7e21e3c" class="outline-4">
<h4 id="org7e21e3c"><span class="section-number-4">2.2.1.</span> <code>multirember</code> (remove member multiple times) function using <code>letrec</code></h4>
<div class="outline-text-4" id="text-2-2-1">
<p>
The following definition of <code>multirember</code> makes use of <code>letrec</code> instead of <code>Y</code>, because the definition of <code>mr</code> inside makes use of <code>mr</code> recursively itself. A normal <code>let</code> would not work here. The recursive <code>mr</code> is then returned and applied to <code>lat</code>, a list of atoms. This chapter introduces <code>letrec</code>.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org28e8458">(define multirember
  (λ (a lat)
    ((letrec
         ([mr (λ (lat)
                (cond
                 [(null? lat) '()]
                 [(eq? a (car lat))
                  (mr (cdr lat))]
                 [else
                  (cons (car lat)
                        (mr (cdr lat)))]))])
       mr)
     lat)))
</pre>
</div>
</div>

<div id="outline-container-orge588824" class="outline-5">
<h5 id="orge588824"><span class="section-number-5">2.2.1.1.</span> Usage</h5>
<div class="outline-text-5" id="text-2-2-1-1">
<div class="org-src-container">
<pre class="src src-scheme" id="orgdca6b96">(multirember 'a '(a b c a d))
</pre>
</div>
</div>
</div>

<div id="outline-container-orgfbe4282" class="outline-5">
<h5 id="orgfbe4282"><span class="section-number-5">2.2.1.2.</span> Result</h5>
<div class="outline-text-5" id="text-2-2-1-2">
<pre class="example" id="org601f624">
(b c d)
</pre>
</div>
</div>

<div id="outline-container-org2145402" class="outline-5">
<h5 id="org2145402"><span class="section-number-5">2.2.1.3.</span> A more readable version</h5>
<div class="outline-text-5" id="text-2-2-1-3">
<p>
Using the following definition, one can avoid 1 wrapping of parentheses of the <code>letrec</code> expression and move it into the value part of the <code>letrec</code> expression:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org7cb3947">(define multirember
  (λ (a lat)
    (letrec
        ([mr (λ (lat)
               (cond
                [(null? lat) '()]
                [(eq? a (car lat))
                 (mr (cdr lat))]
                [else
                 (cons (car lat)
                       (mr (cdr lat)))]))])
      (mr lat))))
</pre>
</div>

<p>
This seems a bit more readable to me.
</p>
</div>
</div>
</div>
</div>

<div id="outline-container-orgc07ab58" class="outline-3">
<h3 id="orgc07ab58"><span class="section-number-3">2.3.</span> <code>multirember</code> with configurable <code>test?</code> predicate</h3>
<div class="outline-text-3" id="text-2-3">
<p>
We can use 1 layer of currying to make a "factory" of <code>multirember</code> functions, which know how to test for whether an element should be removed from a list.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org3f2689d">(define make-multirember
  (λ (test?)
    (λ (a lat)
      (letrec
          ([mr (λ (lat)
                 (cond
                  [(null? lat) '()]
                  [(test? a (car lat))
                   (mr (cdr lat))]
                  [else
                   (cons (car lat)
                         (mr (cdr lat)))]))])
        (mr lat)))))
</pre>
</div>

<div class="org-src-container">
<pre class="src src-scheme" id="org58b2036">(simple-format
 #t "~a\n"
 ((make-multirember =) 1 '(2 4 6 12 1 2)))
</pre>
</div>

<pre class="example" id="org5adaccb">
(2 4 6 12 2)
</pre>
</div>
</div>

<div id="outline-container-org3d9907f" class="outline-3">
<h3 id="org3d9907f"><span class="section-number-3">2.4.</span> Set union implementation</h3>
<div class="outline-text-3" id="text-2-4">
</div>
<div id="outline-container-org421f055" class="outline-4">
<h4 id="org421f055"><span class="section-number-4">2.4.1.</span> First version</h4>
<div class="outline-text-4" id="text-2-4-1">
<div class="org-src-container">
<pre class="src src-scheme" id="org8a26843">(define member? member)

(define union
  (λ (set1 set2)
    (cond
     [(null? set1) set2]
     [(member? (car set1) set2)
      (union (cdr set1) set2)]
     [else
      (cons (car set1)
            (union (cdr set1) set2))])))

(simple-format
 #t "~a\n"
 (union '(a b c d) '(s b a e)))
</pre>
</div>

<pre class="example" id="orgfbb2bd4">
(c d s b a e)
</pre>
</div>
</div>

<div id="outline-container-org55c30ea" class="outline-4">
<h4 id="org55c30ea"><span class="section-number-4">2.4.2.</span> Second version with captured <code>set2</code></h4>
<div class="outline-text-4" id="text-2-4-2">
<p>
The text has objections about the fact, that <code>union</code> is always called with 2 arguments, the 2 sets to build the union of, although <code>set2</code> never changes. It argues, that one can make the recursive calls simpler, by capturing <code>set2</code> outside of the recursive part.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org2963c82">(define member? member)

(define union
  (λ (set1 set2)
    (letrec ([U
              (λ (set1°)
                (cond
                 [(null? set1°) set2]
                 [(member? (car set1°) set2)
                  (U (cdr set1°))]
                 [else
                  (cons (car set1°)
                        (U (cdr set1°)))]))])
      (U set1))))

(simple-format
 #t "~a\n"
 (union '(a b c d) '(s b a e)))
</pre>
</div>

<pre class="example" id="orgbd9a07f">
(c d s b a e)
</pre>
</div>
</div>

<div id="outline-container-org5b59857" class="outline-4">
<h4 id="org5b59857"><span class="section-number-4">2.4.3.</span> Third version with protected <code>member?</code></h4>
<div class="outline-text-4" id="text-2-4-3">
<p>
The text also notes, that <code>union</code> relies on <code>member?</code>, which is implemented elsewhere. <code>union</code> serves as an example. <code>member?</code> or <code>member</code> is usually implemented in Scheme dialects, so it will not suddenly change. However, if it were a function, which were to change for example the order of its arguments, then we would have to adapt <code>union</code> and all other functions depending on <code>member?</code> as well. For this reason, the text argues for internalizing the definition of <code>member?</code> inside of <code>union</code>.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org0854a57">(define union
  (λ (set1 set2)
    (letrec ([U
              (λ (set1°)
                (cond
                 [(null? set1°) set2]
                 [(member? (car set1°) set2)
                  (U (cdr set1°))]
                 [else
                  (cons (car set1°)
                        (U (cdr set1°)))]))]
             [member?
              (λ (elem lst)
                (letrec ([M?
                          (λ (lst°)
                            (cond
                             [(null? lst°) #f]
                             [(eq? elem (car lst°)) #t]
                             [else (M? (cdr lst°))]))])
                  (M? lst)))])
      (U set1))))

(simple-format
 #t "~a\n"
 (union '(a b c d) '(s b a e)))
</pre>
</div>

<pre class="example" id="orgc1c53da">
(c d s b a e)
</pre>
</div>
</div>

<div id="outline-container-org568277c" class="outline-4">
<h4 id="org568277c"><span class="section-number-4">2.4.4.</span> Fourth version</h4>
<div class="outline-text-4" id="text-2-4-4">
<p>
Maybe instead of defining a whole <code>member?</code> inside <code>letrec</code> one could make a minimalistic wrapper for the <code>member</code> function already defined in Scheme. This way we would not reimplement things which are already in our language:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgfe921f4">(define union
  (λ (set1 set2)
    (letrec ([U
              (λ (set1°)
                (cond
                 [(null? set1°) set2]
                 [(member? (car set1°) set2)
                  (U (cdr set1°))]
                 [else
                  (cons (car set1°)
                        (U (cdr set1°)))]))]
             [member?
              (λ (elem lst)
                (letrec ([M?
                          (λ (lst°)
                            (not (null? (member elem lst))))])
                  (M? lst)))])
      (U set1))))

(simple-format
 #t "~a\n"
 (union '(a b c d) '(s b a e)))
</pre>
</div>

<p>
The book has a bootstrapping approach, so it opts to implement <code>member?</code> inside <code>union</code>. A disadvantage of that is, that it cannot be separately unit-tested. Perhaps the philosophy there is, that encapsulation is more important than tests.
</p>
</div>
</div>
</div>
</div>
</div>
<div id="postamble" class="status">
<p class="date">Date: 2021-08-31 Di 00:00</p>
<p class="author">Author: Zelphir Kaltstahl</p>
<p class="date">Created: 2023-02-21 Di 18:07</p>
<p class="validation"><a href="https://validator.w3.org/check?uri=referer">Validate</a></p>
</div>
</body>
</html>